package _stack_queue

import org.junit.Assert
import org.junit.Test
import java.util.*

/**
 * https://leetcode.cn/problems/sliding-window-maximum/
 * https://programmercarl.com/0239.%E6%BB%91%E5%8A%A8%E7%AA%97%E5%8F%A3%E6%9C%80%E5%A4%A7%E5%80%BC.html
 * 239. 滑动窗口最大值
 *
 * 输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
 * 输出：[3,3,5,5,6,7]
 * 解释：
 * 滑动窗口的位置                最大值
 * ---------------               -----
 * [1  3  -1] -3  5  3  6  7       3
 *  1 [3  -1  -3] 5  3  6  7       3
 *  1  3 [-1  -3  5] 3  6  7       5
 *  1  3  -1 [-3  5  3] 6  7       5
 *  1  3  -1  -3 [5  3  6] 7       6
 *  1  3  -1  -3  5 [3  6  7]      7
 * 示例 2：
 *
 * 输入：nums = [1], k = 1
 * 输出：[1]
 *
 */
class leetcode_239 {
    @Test
    fun test_1() {
        val nums = intArrayOf(1, 3, -1, -3, 5, 3, 6, 7)
        val k = 3
        val actual = maxSlidingWindow(nums, k)
        val expect = intArrayOf(3, 3, 5, 5, 6, 7)
        Assert.assertEquals(expect.contentToString(), actual.contentToString())
    }

    @Test
    fun test_2() {
        val nums = intArrayOf(1)
        val k = 1
        val actual = maxSlidingWindow(nums, k)
        val expect = intArrayOf(1)
        Assert.assertEquals(expect.contentToString(), actual.contentToString())
    }

    fun maxSlidingWindow(nums: IntArray, k: Int): IntArray {
        /**
        k = 3
        len = 8
        result =  6
        array len =  len -k + 1
        第一步：先制作一个单调队列（队头对大，队尾最小）
        MyQueue{
        peek()// 队头

        offer(v) // 加入队尾
        {
        队列不为空
        循环 ： 队列不空，且 v 比队尾大，删除队尾，直到 小于队尾
        加入队尾
        }

        poll(v){ // 删除
        与队头相等，才可以可以删除它
        }
        }

        【0,k-1】入队
        peek -> max

        for(i = k to n){
        poll(i-k value)
        offer(i value)
        peek 最大值
        }

        return array
         */
        if (nums.size == 1) {
            return nums
        }
        val result: IntArray = IntArray(nums.size - k + 1)
        val q: MyQueue = MyQueue()

        for (i in 0..k - 1) { // [0,k-1]
            q.offer(nums[i])
        }
        var index: Int = 0
        result[index++] = q.peek()

        for (i in k..nums.size - 1) { // [k,len-1]
            // i = 3 v = -3), 删除 index = 0, v = 1
            q.poll(nums[i - k])
            q.offer(nums[i])
            result[index++] = q.peek()
        }
        return result
    }
}

// 头大，尾巴小
class MyQueue {
    val q: LinkedList<Int> = LinkedList<Int>()

    fun peek(): Int { // head
        return q.peek()
    }

    fun offer(n: Int) { // add to last
        while (!q.isEmpty() && n > q.peekLast()) {
            q.removeLast()
        }
        q.addLast(n)
    }

    fun poll(n: Int) { // head
        if (!q.isEmpty() && q.peek() == n) {
            q.poll()
        }
    }
}